package Heap;

public class MyHeap {

    public int[] arr;
    int size = 0;

    public MyHeap(int capacity) {
        this.arr = new int[capacity];
    }

    public MyHeap() {
    }

    public MyHeap(int[] arr) {
        this.arr = arr;
        size = arr.length;
        heapify();
    }

    //判断当前数组是否为空
    private boolean isEmpty() {
        return size == 0;
    }

    //判断当前数组是否满了
    private boolean isFull() {
        return size == arr.length;
    }

    //查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return arr[0];
    }

    //下潜
    private void down(int i) {

        int left = 2*i+1;
        int right = left + 1;
        int max = i;
        if (left < size && arr[max] < arr[left]) {
            max = left;
        }
        if (right < size && arr[max] < arr[right]) {
            max = right;
        }
        if (i != max) {
            //先交换
            swap(i,max);
            //再下潜
            down(max);
        }

    }

    //交换
    private void swap(int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //删除栈顶元素
    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        //先记录返回值
        int ret = arr[0];
        //交换元素
        swap(0,size - 1);
        //数据个数 - 1
        size--;
        //下潜
        down(0);
        return ret;
    }

    //指定删除元素下标
    public int poll(int i) {
        if (i > size) {
            return -1;
        }
        int ret = arr[i];
        swap(i,size - 1);
        size--;
        down(i);
        return ret;
    }

    //添加元素
    public boolean offer(int value) {
        if (isFull()) {
            return false;
        }
        int j = (size - 1) / 2;
        int i = size;
        while (i > 0 && arr[j] < value) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;

    }

    //建堆
    public void heapify() {
        int last = size / 2 - 1;
        for (int i = last ; i >= 0; i --) {
            down(i);
        }
    }

    //堆排序
    public int[] heapSort (int[] arr){
        //建立大根堆
        int size = arr.length;
        int last = size / 2 - 1;
        for (int i = last; i >= 0; i--) {
            down(i);
        }
        //最后一个元素与堆顶元素进行交换
        for (int j = size - 1; j >= 0; j--) {
            swap(j,0);
            down(0);
        }
        return arr;

    }

}
